﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>

#define INIT_LIST_LENGTH 1

typedef int SLTypeData;
typedef struct SequenceList
{
	SLTypeData* sl;
	int size;
	int capacity;
}SequenceList;

void InitSeqList(SequenceList*const s)
{
	assert(s);
	s->sl = (SLTypeData*)malloc(INIT_LIST_LENGTH*sizeof(SLTypeData));
	if (NULL == s->sl)
	{
		perror("InitSeqList");
		exit(-1);
	}
	s->size = 0;
	s->capacity = INIT_LIST_LENGTH;
}

void IncreaseCapacity(SequenceList* const s)
{
	assert(s);
	SLTypeData* t = NULL;
	t = (SLTypeData*)realloc(s->sl, 2 * s->capacity * sizeof(SLTypeData));
	if (NULL == t)
	{
		perror("IncreaseCapacity");
		exit(-1);
	}
	s->sl = t;
	s->capacity = 2 * s->capacity;
}

void SLPrint(const SequenceList* const s)
{
	assert(s);
	assert(s->sl);
	int i = 0;
	for (i = 0; i < s->size; ++i)
	{
		printf("%d ", *(s->sl + i));
	}
	putchar('\n');
}

void DestorySL(SequenceList* s)
{
	assert(s);
	free(s->sl);
	s->sl = NULL;
	s->size = 0;
	s->capacity = 0;
}

void SeqListPushBack(SequenceList* s,const SLTypeData data)
{
	assert(s);
	assert(s->sl);
	if (s->size == s->capacity)
	{
		IncreaseCapacity(s);
	}
	*(s->sl + s->size) = data;
	s->size++;
}

SLTypeData SeqListPopBack(SequenceList* const s)
{
	assert(s);
	assert(s->sl);
	assert(s->size > 0);
	s->size--;
	return *(s->sl + s->size);
}

void SeqListPushFront(SequenceList* s,const SLTypeData data)
{
	assert(s);
	assert(s->sl);
	if (s->size == s->capacity);
	{
		IncreaseCapacity(s);
	}
	int i = s->size;
	for (; i >= 1; --i)
	{
		*(s->sl + i) = *(s->sl + i - 1);
	}
	*(s->sl) = data;
	s->size++;
}

SLTypeData SeqListPopFront(SequenceList* const s)
{
	assert(s);
	assert(s->sl);
	assert(s->size > 0);
	SLTypeData t = *(s->sl);
	int i = 0;
	for (i = 0; i < s->size-1; ++i)
	{
		*(s->sl + i) = *(s->sl + i + 1);
	}
	s->size--;
	return t;
}

int SeqListFind(const SequenceList* const s,const SLTypeData data)
{
	assert(s);
	assert(s -> sl);
	assert(s->size > 0);

	int i = 0;
	for (i = 0; i < s->size; ++i)
	{
		if (*(s->sl + i) == data)
		{
			return i;
		}
	}
	return -1;
}

void SeqListInsert(SequenceList* s,const int pos,const SLTypeData data)
{
	assert(s);
	assert(s -> sl);
	assert(s->size > 0);

	if (pos<0 || pos>s->size)
	{
		perror("SeqListInsert");
		return;
	}
	if (s->size == s->capacity)
	{
		IncreaseCapacity(s);
	}
	int i = s->size;
	for (; i > pos; --i)
	{
		*(s->sl + i) = *(s->sl + i - 1);
	}
	*(s->sl + i) = data;
	s->size++;
}

SLTypeData SeqListErase(SequenceList* const s, const int pos)
{
	assert(s);
	assert(s->sl);

	if (pos<0 || pos>s->size)
	{
		perror("SeqListErase");
		return NULL;
	}
	int i = pos;
	SLTypeData t = *(s->sl + pos);
	for (; i+1 < s->size; ++i)
	{
		*(s->sl + i) = *(s->sl + i + 1);
	}
	s->size--;

	return t;
}

void test(SequenceList* s)
{
	InitSeqList(s);
	SeqListPushBack(s, 1);
	SeqListPushBack(s, 7);
	SeqListPushFront(s, 3);
	SeqListPushFront(s, 9);
	printf("%d\n", SeqListFind(s, 7));
	SLPrint(s);
	SeqListInsert(s, 3, 11);
	SLPrint(s);
	SeqListErase(s, 1);
	SLPrint(s);
	//SeqListPopBack(s);
	//SLPrint(s);
	//SeqListPopFront(s);
	//SLPrint(s);
	//SeqListPopFront(s);
	DestorySL(s);
}

int main(void)
{
	SequenceList s;
	test(&s);

	return 0;
}

/*
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值
等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
*/
int removeElement(int* nums, int numsSize, int val)
{
	int front = 0;
	int rear = 0;
	for (front = 0; front < numsSize; ++front)
	{
		if (nums[front] == val)
		{
			break;
		}
	}
	for (rear = front + 1; rear < numsSize; ++rear)
	{
		if (nums[rear] != val)
		{
			nums[front] = nums[rear];
			front++;
		}
	}

	return front;
}